#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define MAXV 100
#define INF INT_MAX
typedef char InfoType;

typedef struct ANode {
	int adjvex;                  // 邻接点编号
	struct ANode* nextarc;      // 指向下一条边的指针
	int weight;                  // 权值
} ArcNode;                      // 边结点类型

typedef struct Vnode {
	InfoType info[20];				//顶点其他信息	
	ArcNode* firstarc;          // 指向第一条边
} VNode;                       // 邻接表头结点类型

typedef struct {
	VNode adjlist[MAXV];       // 邻接表头结点数组
	int n, e;                  // 图中顶点数n和边数e
} AdjGraph;                   // 完整的图邻接表类型

void CreateAdj(AdjGraph* G, int A[MAXV][MAXV], int n, int e) {
	int i, j;
	ArcNode* p;
	G->n = n;
	G->e = e;
	for (i = 0; i < n; i++) {
		G->adjlist[i].firstarc = NULL;
	}
	for (i = 0; i < n; i++) {
		for (j = 0; j < n; j++) {
			if (A[i][j] != 0 && A[i][j] != INF) { // 存在边
				p = (ArcNode*)malloc(sizeof(ArcNode));
				p->adjvex = j;
				p->weight = A[i][j];
				p->nextarc = G->adjlist[i].firstarc; // 头插法
				G->adjlist[i].firstarc = p;
			}
		}
	}
}

void DispAdj(AdjGraph *G)	//输出邻接表G
{
	int i;
	ArcNode *p;
	for (i=0;i<G->n;i++)
	{
		p=G->adjlist[i].firstarc;
		printf("%3d: ",i);
		while (p!=NULL)
		{
			printf("%3d[%d]→",p->adjvex,p->weight);
			p=p->nextarc;
		}
		printf("∧\n");
	}
}

void DestroyAdj(AdjGraph *&G)		//销毁图的邻接表
{	
	int i;
	ArcNode *pre,*p;
	for (i=0;i<G->n;i++)			//扫描所有的单链表
	{	
		pre=G->adjlist[i].firstarc;	//p指向第i个单链表的首结点
		if (pre!=NULL)
		{	
			p=pre->nextarc;
			while (p!=NULL)			//释放第i个单链表的所有边结点
			{	
				free(pre);
				pre=p; 
				p=p->nextarc;
			}
			free(pre);
		}
	}
	free(G);						//释放头结点数组
}

int count = 0;
int visited[MAXV] = {0}; // 访问标记
int path[MAXV]; // 存储路径
int totalWeight = 0; // 存储总权值
int pathIndex = 0;

void DFS(AdjGraph*& g, int current, int destination, int pathIndex) {
	visited[current] = 1; // 标记已访问
	path[pathIndex] = current;
	pathIndex++;
	
	// 如果到达目标结点，打印路径和总权值
	if (current == destination) {
		printf("路径: ");
		for (int i = 0; i < pathIndex; i++) {
			if (path[i] == 0) printf("北京->");
			else if (path[i] == 1) printf("武汉->");
			else if (path[i] == 2) printf("广州->");
			else if (path[i] == 3) printf("郑州->");
			else if (path[i] == 4) printf("成都->");
			else if (path[i] == 5) printf("昆明->");
			else if (path[i] == 6) printf("富宁->");
			else if (path[i] == 7) printf("普者黑");
		}
		printf("，总价: %d\n", totalWeight);
		count++;
	} else {
		ArcNode* p = g->adjlist[current].firstarc;
		while (p != NULL) {
			if (!visited[p->adjvex]) {
				totalWeight += p->weight;
				DFS(g, p->adjvex, destination, pathIndex);
				totalWeight -= p->weight; // 回溯
			}
			p = p->nextarc;
		}
	}
	
	visited[current] = 0; // 标记为未访问
	pathIndex--; // 回溯
}

int minWeight = INF; 
int bestPath[MAXV]; 
int bestPathLength = 0;
void DFS2(AdjGraph*& g, int current, int destination, int pathIndex) {
	visited[current] = 1; // 标记已访问
	path[pathIndex] = current;
	pathIndex++;
	
	// 如果到达目标结点
	if (current == destination) {
		if (totalWeight < minWeight) {
			minWeight = totalWeight;
			memcpy(bestPath, path, sizeof(int) * pathIndex);
			// 更新路径长度
			bestPathLength = pathIndex;
		}
	} else {
		ArcNode* p = g->adjlist[current].firstarc;
		while (p != NULL) {
			if (!visited[p->adjvex]) {
				totalWeight += p->weight;
				DFS2(g, p->adjvex, destination, pathIndex);
				totalWeight -= p->weight; // 回溯
			}
			p = p->nextarc;
		}
	}
	
	visited[current] = 0; // 标记为未访问
	pathIndex--; // 回溯
}

void PrintPath(int pathIndex) {
	for (int i = 0; i < bestPathLength; i++) {
		if (bestPath[i] == 0) printf("北京->");
		else if (bestPath[i] == 1) printf("武汉->");
		else if (bestPath[i] == 2) printf("广州->");
		else if (bestPath[i] == 3) printf("郑州->");
		else if (bestPath[i] == 4) printf("成都->");
		else if (bestPath[i] == 5) printf("昆明->");
		else if (bestPath[i] == 6) printf("富宁->");
		else if (bestPath[i] == 7) printf("普者黑");
	}
	printf("\n");
}

int main() {
	int A9g3[MAXV][MAXV] = {
		{0, 152, 251, 93, 240, 302, INF, INF}, // 0
		{152, 0, 138, 75, 183, 217, INF, INF}, // 1
		{251, 138, 0, 192, 206, 192, 299, 360}, // 2
		{93, 75, 192, 0, 192, 268, INF, INF}, // 3
		{240, 183, 206, 192, 0, 500, INF, INF}, // 4
		{320, 217, 192, 268, 500, 0, 363, 75}, // 5
		{INF, INF, 299, INF, INF, 363, 0, 50}, // 6
		{INF, INF, 360, INF, INF, 75, 50, 0} // 7
	};
	
	int n9g3 = 8, e9g3 = 20; // 边数可以根据实际情况设置
	
	AdjGraph* g9g3;
	g9g3 = (AdjGraph*)malloc(sizeof(AdjGraph));
	CreateAdj(g9g3, A9g3, n9g3, e9g3);
	
	DispAdj(g9g3);
	int source = 0;
	int destination = 7;
	printf("所有路径:\n");
	DFS(g9g3, source, destination ,0);
	printf("count = %d\n", count);
	
	printf("花费最少的路径：\n");
	DFS2(g9g3, source, destination, 0);
	if (minWeight != INF) {
		PrintPath(pathIndex); // 仅打印最佳路径
		printf("最短路径总价: %d\n", minWeight);
	} else {
		printf("没有找到从北京到普者黑的路径。\n");
	}
	
	DestroyAdj(g9g3);
	
	return 0;
}

